This application includes Appendix A containing computer code that performs compression of image data in accordance with this invention and Appendix B containing computer code that performs decompression of image data in accordance with this invention.
A portion of the disclosure of this patent document contains material which is subject to (copyright or mask work) protection. The (copyright or mask work) owner has no objection to the facsimile reproduction by any-disclosure, as it appears in the Patent and otherwise Office patent file or records, but otherwise reserves all (copyright or mask work) rights whatsoever.
1. Field of Invention
This invention relates generally to compression and decompression systems and methods. More specifically, this invention relates to compression and decompression systems and methods that compress and decompress image areas containing edges of marks to be rendered in image data based on the direction of the edges of the marks.
2. Description of Related Art
The human viewer appreciates viewing non-continuous toneart information, e.g., text and/or lineart, at higher spatial resolutions than the spatial resolutions required for continuous toneart information, e.g., halftone information, because the human eye sees contrast information at a higher spatial resolution than color information. Therefore, more spatial resolution is necessary to render non-continuous tone regions than is necessary to render continuous tone regions. This differentiation between the amount of information necessary for the human eye to process non-continuous tone regions and to process continuous tone regions is due to hyperacuity. Hyperacuity is the human visual system""s ability to differentiate locally misaligned edges of marks in a rendered image to a much finer extent than the receptor spacing of the human eye. It is not the frequency response, i.e., resolution, of the visual system, but the ability to reckon edge position with high precision that is most important.
Data transmitted in a bytemap, i.e., one byte for each pixel of the image, typically has a corresponding spatial resolution that is roughly equal to the size of the pixel. Forming high quality continuous tone regions does not require as much spatial resolution for the transmitted data. However, continuous tone regions require a high number of tone levels to minimize contouring, or the ability of the visual system to see changes in tone. In contrast, forming extremely detailed non-continuous tone marks, such as three or four point text, requires a significant amount of spatial resolution for the transmitted image data, but generally requires fewer number of tone levels.
In this case, the non-continuous tone pixels are not necessarily binary, but can also be composed of a number of gray levels. The non-continuous tone data is of the type that might be scanned in from a high quality scanner, or of a type called antialiased, which contains partial intensities to help in the removal of stairstepping or the positioning of edges.
Therefore, in a bytemap, high spatial resolution, e.g., 800xc3x97800 pixels per inch (ppi) is necessary for non-continuous tone regions, while continuous tone regions only need low spatial resolution, e.g., 400xc3x97400 (ppi). Therefore, transmitting bytemapped image data with high spatial resolution results in an unnecessary degree of spatial resolution for rendering continuous tone data and a waste of image system resources to process the unnecessary data.
If bitmaps are used instead to transmit image data for printing, continuous tone data is sent as prehalftoned dot shapes. Sending proper pre-halftoned dots to a destination, e.g., a printer, requires a high spatial resolution, e.g., 600xc3x974800 ppi, to avoid contouring. However, 4800 pixels per inch resolution is too much resolution for non-continuous tone data.
Therefore, when using bitmaps, higher spatial resolution is necessary for rendering continuous tone data than is necessary for rendering non-continuous tone data, once again resulting in a waste of image system resources to process the unnecessary data.
Regardless of whether the bitmaps or bytemaps are used to render images, spatial resolution mismatch results because of the different requirements for rendering non-continuous tone data and continuous tone data. Nevertheless, conventionally, continuous tone data, e.g., halftone data, and non-continuous tone data, e.g., text and lineart data, are sent to a printer or associated hardware that convert bytemaps or bitmaps into scanning laser modulations at essentially the same spatial resolution.
Thus, this invention provides compression and decompression systems and processes for compressing and decompressing image data taking the resolution mismatch into consideration. In one exemplary embodiment of the compression and decompression systems and methods, regions of an image are optimally compressed and decompressed based on the composition of the regions, for example, whether the regions are continuous tone or non-continuous tone regions.
This invention separately provides compression and decompression systems and methods that at least double the spatial resolution for non-continuous tone data, while maintaining adequate spatial resolution for continuous tone data and minimizing the amount of memory and corresponding transmission bandwidth requirements.
The invention separately provides compression and decompression systems and methods for storing extra resolution in a frequency spatial resolution direction of non-continuous tone data to improve the appearance of an image rendered using the data.
The invention separately provides compression and decompression systems and methods that eliminate spatial resolution mismatch between data used to render continuous tone regions and data used to render non-continuous tone regions.
This invention separately provides compression and decompression systems and methods that provide the necessary information to provide high spatial resolution non-continuous tone data and low spatial resolution continuous tone data as compressed data.
The invention separately provides compression and decompression systems and methods that increase non-continuous tone data spatial resolution.
The invention separately provides compression and decompression systems and methods that render gray level information for two non-continuous tone pixels in a single byte.
The invention separately provides decompression systems and methods that typically double the spatial resolution of non-continuous tone data relative to the compressed data. That is, during compression, the compressed data is abbreviated in the high frequency spatial resolution direction, i.e., the directed acuity direction, which is the direction perpendicular to the edge.
According to the compression and decompression systems and processes of this invention, a bytemap is asymmetrically compressed and decompressed. During compression, either a low spatial resolution or high spatial resolution bytemap is divided into data blocks and segmented so that the continuous toneart data regions are separated from the non-continuous tone data regions. The segmented bytemap data is processed to provide both low spatial resolution continuous tone data and high spatial resolution non-continuous tone data.
Specifically, the high spatial resolution non-continuous tone data is compressed by quantizing and packing high resolution pixels in a direction across the edge, i.e., perpendicular to an edge of a mark to be rendered, and discarding high resolution pixels along the edge, i.e., parallel to the edge. Additional information, called tag bits, indicating the directions of the edges, e.g., vertical or horizontal directions, and the type of image data, e.g., continuous or non-continuous data, is also stored to enable decompression.
Subsequently, during decompression, the non-continuous tone data is decompressed into a high spatial resolution bytemap by unpacking the high resolution pixels across the edge, and inferring the high resolution pixels along the edge. The low spatial resolution continuous tone data are processed to provide a low spatial resolution continuous tone bytemap, which will later be halftoned.
As a result of compression and decompression systems and methods according to this invention, the amount of memory necessary to store the non-continuous tone data is reduced to a quarter of the memory necessary to store a conventional high spatial resolution bytemap. Corresponding improvements in bandwidth utilization accompany this reduction in memory requirements. As a result, the resolution mismatch present in conventional image rendering is eliminated because high spatial resolution bytemap data is provided for the non-continuous tone regions, while low spatial resolution bytemap data is provided for continuous tone regions without any waste of printer resources.
Accordingly, the compression and decompression systems and processes of this invention take into consideration whether a byte represents continuous tone data, or non-continuous tone data. During compression of non-continuous tone, two out of four high spatial resolution antialiased non-continuous tone pixels are discarded and the other two are compressed into a single byte.
The increased spatial resolution of the non-continuous tone data is beneficial because a 400 byte per inch (bpi) compressed data bytemap with high quality continuous tone data can produce non-continuous tone data at a spatial resolution of 800xc3x97800 bpi, for instance. This occurs because, when bytemaps are used, halftoning is performed and the printer and the quality of the halftone dots is stored in the printer.
In the compressed data according to the systems and method of this invention, only eight levels of gray are available for non-continuous tone data, as opposed to 128 levels of gray for the compressed continuous tone data. Although some measure of precision is lost by rendering the non-continuous tone regions using eight rather than 256 levels of gray, the loss in precision is negligible in comparison to the improved memory and printer resource utilization. In this case, there is a two-fold compression in each direction, which is an overall four-fold two-dimensional compression.
This invention can be implemented with alternate quantizing and packing formatting, for instance quantizing to four or two (binary) levels of gray for the non-continuous tone levels, in which case even more compression would be possible. For example, four levels of gray are implemented with two bits, and three of these two-bit values can be packed into the same six bits that two three-bit values are stored. This would give a three-fold compression in one direction, or a nine-fold two-dimensional compression. Likewise, using binary values would provide a six-times compression in one direction, which is a thirty-six-fold 2-D compression.
Additionally, there are many possible pixel word lengths besides six bits (plus the two tag bits), which increases the permutations of possible compression formatting.
In one exemplary embodiment of the compression and decompression systems and methods, regions of an image are optimally compressed and decompressed based on the composition of the regions, for example, whether the regions are continuous tone or non-continuous tone regions.
In a first exemplary embodiment of the compression and decompression systems and methods of this invention, during compression, a high spatial resolution bytemap output from an image source is processed to provide high spatial resolution continuous tone data and high spatial resolution non-continuous tone data. During compression, three-quarters of the pixels identified as continuous tone data are discarded to produce low spatial resolution continuous tone data. Also, half of the pixels identified as non-continuous tone data are discarded, but only in the direction along the edge. Specifically, half of the non-continuous tone pixels are discarded in such a manner that high spatial resolution is maintained in the directions across edges of marks in the image, but low spatial resolution is provided in directions parallel to those edges. Therefore, low spatial resolution continuous tone data and one-dimensional high spatial resolution non-continuous tone data are produced.
Additionally, information regarding two pixels of non-continuous tone data are compressed into a single data word, e.g., a byte. However, information regarding only one pixel of continuous tone data is included in each byte of compressed image data. The memory necessary to store the non-continuous tone data is decreased to a quarter of the original memory because half of the pixels of the non-continuous tone data are discarded in the directions parallel to the edges and the data of two non-continuous tone data pixels is compressed into a single byte of image data. Corresponding improvements in bandwidth utilization accompany this reduction in the required memory.
The data corresponding to each of the two non-continuous tone pixels is contained in three-bits of data in the compressed data bytes. Therefore, six bits of a compressed data byte contain data corresponding to two non-continuous tone pixels. The remaining two bits of each compressed data byte are a segmentation bit, indicating whether the byte is continuous tone data or non-continuous tone data, and a direction bit, indicating the direction of an edge located between the pixel corresponding to the byte of data if the data is non-continuous tone data. This direction bit, in turn, indicates the direction of fabrication to be performed when decompressing the compressed data byte. Thus, each byte of compressed image data includes a segmentation bit that indicates whether the data stored in the byte is non-continuous tone data, or a continuous tone data. If the byte of compressed image data contains non-continuous tone data, the byte also includes the direction bit which classifies the direction of the edge located between the two pixels of that the byte.
During compression, the high spatial resolution non-continuous tone data is compressed into a high spatial resolution bytemap with extra resolution along the edges. The low resolution continuous tone data are processed to provide a low spatial resolution continuous tone bytemap. During decompression, the image values associated with the discarded pixels of non-continuous tone data are synthesized from the information in adjacent compressed data bytes. Specifically, discarded pixels can be inferred by interpolating in the direction along the edge between two adjacent non-continuous tone pixels.
In a second exemplary embodiment of the compression and decompression systems and methods of this invention, an image source produces low spatial resolution continuous tone data and high spatial resolution non-continuous tone data. The high spatial resolution non-continuous tone data is compressed in the same manner as in the first exemplary embodiment. The low spatial resolution continuous tone data does not need to be compressed. The resulting compressed non-continuous tone data is decompressed in the same manner as in the first embodiment to provide high spatial resolution non-continuous tone data. Similarly to the first exemplary embodiment, during decompression, the low spatial resolution continuous tone data is processed to provide low spatial resolution data.
In a third exemplary embodiment of the compression and decompression systems and method of this invention, an image source produces low spatial resolution continuous tone data. The image source also produces non-continuous tone data that has high spatial resolution only in directions across the edges. As a result, there is no need to increase a bytemap size by four times to provide twice as much resolution. Therefore, the process may use a bytemap that is a quarter the size of the bytemap that would otherwise be conventionally necessary to provide high spatial resolution non-continuous tone data. During the compression according to this third exemplary embodiment of the systems and methods of this invention, no pixels are discarded from the non-continuous tone data or the continuous tone data.
These and other features and advantages of this invention are described in or are apparent from the following detailed description of the systems and methods according to this invention.